package com.ankie.algorithm;

import com.sun.org.apache.bcel.internal.generic.SWAP;

import java.util.Arrays;

/**
 * @ClassName ShellSort
 * @Author ankie
 * @Date 2020/6/8
 * @Description // TODO
 */
public class ShellSort {

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    private static void shellSort(int[] arr) {
        int len = arr.length;
        // 这里是设置每次循环的间隔，gap在希尔算法最开始使用的就是每次取区间值的一半，
        // 可以自己设定gap固定值进行缩减：如：4、3、2、1，最后间隔为1
        for (int gap = len / 2; gap > 0; gap = gap / 2) {
            // 实际是多个分组交替执行
            for (int i = gap; i < len; i++) {
                for (int j = i; j > gap - 1; j -= gap) {
                    if (arr[j] < arr[j - gap]) {
                        swap(arr, j, j - gap);
                    }
                }
            }
        }
    }

    /**
     * Knuth 序列，优化之后计算gap间距的方法
     */
    private static void shellKnuthSort(int[] arr) {
        int len = arr.length;
        int h = 1;
        // 计算 h 开始的间距的值
        while (h < len / 3) {
            h = h * 3 + 1;
        }
        // 这里是设置每次循环的间隔，gap在Knuth序列方式下可以更快一点
        for (int gap = h; gap > 0; gap = (gap - 1)/ 3) {
            // 实际是多个分组交替执行
            for (int i = gap; i < len; i++) {
                for (int j = i; j > gap - 1; j -= gap) {
                    if (arr[j] < arr[j - gap]) {
                        swap(arr, j, j - gap);
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {3, 44, 38, 5, 47, 15, 36, 26, 66, 29, 50, 48, 27};
        System.out.println(Arrays.toString(arr));
        shellSort(arr);
        System.out.println(Arrays.toString(arr));
        int[] arr1 = {3, 44, 38, 5, 47, 15, 36, 26, 66, 29, 50, 48, 27};
        System.out.println(Arrays.toString(arr1));
        shellKnuthSort(arr1);
        System.out.println(Arrays.toString(arr1));
    }
}
